/*
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;



struct node {
	ElemType data;
	struct node *next;
};

struct link_queue {
	struct node *front;
	struct node *rear;
};

typedef struct link_queue link_queue_t;



/*
 * 初始化队列，带头结点
 */
int
init_queue(link_queue_t *q)
{
    struct node *ptr;
    ptr = malloc(sizeof(struct node));
    if (ptr == NULL)
        return -1;

    memset(&ptr->data, 0, sizeof(ElemType));
    ptr->next = NULL;

    /* 头指针/尾指针 指向头结点 */
	q->front = q->rear = ptr;
    
    return 0;
}



/*
 * 入队
 */
int
enqueue(link_queue_t *q, ElemType *item)
{
	struct node *ptr;
	ptr = (struct node *) malloc(sizeof(struct node));

	ptr->next = NULL;
	ptr->data = *item;


    q->rear->next = ptr;
    q->rear = ptr;

	return 0;
}

/*
 * 出队
 */
int
dequeue(link_queue_t *q, ElemType *item)
{
	/* if empty */
	if (q->front == q->rear)
		return -1;

	struct node *ptr;
	ptr = q->front->next;

	*item = ptr->data;
	q->front->next = ptr->next;

	/* after delete the last item, rear point to head */
	if (q->rear == ptr)
		q->rear = q->front;
	free(ptr);

	return 0;
}

int
is_queue_empty(link_queue_t *q)
{
    return q->front == q->rear;
}


/*
 * 清空队列
 */
int
clear_queue(link_queue_t *q)
{
    ElemType item;
    while (dequeue(q, &item) != -1)
        continue;
    
    return 0;
}


/*
 * 获取队列头元素
 */
int
get_queue_head(link_queue_t *q, ElemType *item)
{
	/* if empty */ 
	if (q->front == q->rear)
		return -1;
    
    *item = q->front->next->data;
    
    return 0;
}


/******************************************************************************/


int
main(void)
{
    link_queue_t queue;
    int i, ret;
    ElemType item;

    init_queue(&queue);

    printf("After init, is_queue_empty() = %d\n", is_queue_empty(&queue));


    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("enqueue() item[%d] ret[%d]\n", i, enqueue(&queue, &item));
    }
    printf("\n");
    printf("After enqueue, is_queue_empty() = %d\n", is_queue_empty(&queue));



    memset(&item, 0, sizeof(item));
    get_queue_head(&queue, &item);
    printf("After enqueue, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);


    printf("\n");
    /* 删除10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        ret = dequeue(&queue, &item);
        printf("dequeue() item[%d] ret[%d]\n", i, ret);
        if (ret == 0)
            printf("-- Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    }
    printf("After dequeue, is_queue_empty() = %d\n", is_queue_empty(&queue));


    clear_queue(&queue);
    clear_queue(&queue);

    printf("\n");
    printf("After clear, is_queue_empty() = %d\n", is_queue_empty(&queue));
    



    /* 插入6个节点 */
    for (i = 0; i < 6; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("enqueue() item[%d] ret[%d]\n", i, enqueue(&queue, &item));
    }
    printf("\n");
    printf("After enqueue, is_queue_empty() = %d\n", is_queue_empty(&queue));


    memset(&item, 0, sizeof(item));
    get_queue_head(&queue, &item);
    printf("After enqueue, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);


    /* 删除2个节点 */
    for (i = 0; i < 2; ++i) {
        memset(&item, 0, sizeof(item));
        ret = dequeue(&queue, &item);
        printf("dequeue() item[%d] ret[%d]\n", i, ret);
        if (ret == 0)
            printf("-- Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    }
    printf("After dequeue, is_queue_empty() = %d\n", is_queue_empty(&queue));
    
    clear_queue(&queue);

    printf("\n");
    printf("After clear, is_queue_empty() = %d\n", is_queue_empty(&queue));


    return 0;
}

